//
// Created by huili on 2022/3/5.
//

#include <limits.h>

#define MAX(a, b) (((a) >= (b)) ? (a) : (b))
#define MIN(a, b) (((a) <= (b)) ? (a) : (b))


double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){
    int halfSize;
    int head1, tail1, half1, half2;
    int nums1Left, nums1Right, nums2Left, nums2Right;
    double ret;

    //确保nums1Size比较小
    if(nums1Size > nums2Size){
        return findMedianSortedArrays(nums2, nums2Size, nums1, nums1Size);
    }

    //插空后，nums1和nums2的长度均为2numsSize+1，halfSize为两个合起来的长度的一半。
    halfSize = nums1Size + nums2Size;

    //开始对nums1进行二分
    head1 = 0;
    tail1 = 2 * nums1Size;

    //小于等于可包含为空的情况
    while (head1 <= tail1) {
        half1 = head1 + (tail1 - head1) / 2;
        //由于确保nums1Size比较小，half2肯定大于0
        half2 = halfSize - half1;

        //考虑边界情况
        nums1Left = (half1 == 0) ? INT_MIN : nums1[(half1 - 1) / 2];
        nums2Left = (half2 == 0) ? INT_MIN : nums2[(half2 - 1) / 2];

        nums1Right = (half1 == 2 * nums1Size) ? INT_MAX : nums1[half1 / 2];
        nums2Right = (half2 == 2 * nums2Size) ? INT_MAX : nums2[half2 / 2];

        if (nums1Left > nums2Right) {
            tail1 = half1 - 1;
        } else if (nums2Left > nums1Right ) {
            head1 = half1 + 1;
        } else {
            break;
        }
    }

    ret = (MAX(nums1Left, nums2Left) + MIN(nums1Right, nums2Right)) / 2.0;

    return ret;
}

